11177. Корова

Беси стоит перед огромным камнем в середине своего любимого поля. На камне – шифровка на древнем языке, алфавит которого состоит только из трёх букв C, O, W. Беси интересно, сколько раз встретилось слово COW в тексте.

Бесси не возражает если другие букв встречаются между C O W. Также Беси считает разными слова, в которых отличается хоть одна буква. Например COW встречается только один раз в слове CWOW, два раза в слове CCOW и 8 раз в слове CCOOWW.

По заданному тексту шифровки помогите Беси посчитать сколько раз появится слово COW.

Вход. Первая строка содержит одно целое число n (n ≤ 10⁵). Вторая строка содержит строку из n символов, каждый их которых либо C, либо O, либо W.

Выход. Выведите количество раз, которое COW появляется как подпоследовательность, необязательно непрерывная, во входной строке.

Заметим, что ответ может быть очень большим, поэтому используйте 64-битный целочисленный тип.

Пример входа	Пример выхода
12 COWCOWCOWCOW	20

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Будем подсчитывать:

· количество букв C в переменной с;

· количество слов CO в переменной co;

· количество слов COW в переменной cow;

Пусть текущей буквой является C. Тогда увеличим c на 1.

Пусть текущей буквой является O. Тогда она может образовать слово CO с любой из предыдущих с букв C. Для каждой буквы O к co следует прибавить c.

Пусть текущей буквой является W. Тогда она может образовать слово COW с любым из предыдущих co слов CO. Для каждой буквы W к cow следует прибавить co.

Пример

Рассмотрим значения переменных c, co и cow при решении задачи.

Реализация алгоритма

Читаем входные данные.

cin >> n >> s;

Инициализируем переменные.

c = co = cow = 0;

Последовательно обрабатываем буквы строки. В зависимости от текущей буквы s[i] увеличиваем переменную c, co или cow.

for (i = 0; i < n; i++)

if (s[i] == 'C') c++; else

if (s[i] == 'O') co += c; else

if (s[i] == 'W') cow += co;

Выводим ответ.

cout << cow << endl;

Python реализация

Читаем входные данные.

n = int(input())

s = input()

Инициализируем переменные.

c = co = cow = 0

Последовательно обрабатываем буквы строки. В зависимости от текущей буквы s[i] увеличиваем переменную c, co или cow.

for i in range(n):

if s[i] == 'C': c += 1

if s[i] == 'O': co += c

if s[i] == 'W': cow += co

Выводим ответ.

print(cow)